Fibonacci Machine

Memory limit: 32 MB

The Fibonacci numbers are defined as follows:

The Fibonacci machine operates on an -element integer register sequence which initially contains zeroes only. The machine provides two operations:

• adding one to each register in interval , i.e. adding 1 to the numbers ;
• calculating the sum of those Fibonacci numbers, the sequence numbers of which are stored in registers from the interval , i.e. calculating

Input

The first line of the standard input contains two integers and (), separated by a single space and representing the length of the sequence and the number of operations. Each of the following lines contains a description of one operation. Such a description consists of a character D or S and two integers and (), separated by single spaces. The character D stands for adding of 1 to the interval , and the character S stands for calculating the sum of Fibonacci numbers the sequence numbers of which are from . You may assume that at least one operation of type S appears in the sequence of operations.

Output

For each operation S write to the standard output exactly one line with the desired Fibonacci sum. Each result should be calculated modulo .

Example

For the input data:

5 7
D 1 4
S 1 5
D 3 5
D 2 3
S 1 5
D 2 5
S 2 3

the correct result is:

4
6
5

Explanation of the example: After seven operations the sequence of registers becomes . The result of the last query is equal to .

Task author: Tomasz Idziaszek.